Subset selection for the least probable multinomial cell

Summary An inverse sampling procedureR is proposed for selecting a randomsize subset which contains the least probable cell (i.e., the cell with the smallest cell probabilities) from a multinomial distribution withk cells. Type 2-Dirichlet integrals are used (i) to express the probability of a correct selection in terms of integrals with parameters only in the limits of integration, (ii) to prove that the least favorable configuration underR is the so-called slippage configuration withk equal cell probabilities, and (iii) to express exactly the expectation of the total number of observations required and the expectation of the subset size under the procedureR.     

树图的1—Hamilton连通性

一阶数≥3的简单连通图叫做1-Hamilton连通的,若对每一对顶点v_1、v_2及任一边v_2v_3(v_1≠v_3),存在连接v_1和v_2,并且经过v_3v_2的Hamilton路.本文中我们证明:连通图的树图或是1-Hamilton连通的,或为一超立方体,或同构于K_2×K_3和W_5之一.     

The reduction of graph families closed under contraction

Let be a family of graphs. Suppose there is a nontrivial graph H such that for any supergraph G of H, G is in if and only if the contraction G/H is in . Examples of such an : graphs with a spanning closed trail; graphs with at least k edge-disjoint spanning trees; and k-edge-connected graphs (k fixed). We give a reduction method using contractions to find when a given graph is in and to study its structure if it is not in . This reduction method generalizes known special cases.     

On the core and nucleolus of minimum cost spanning tree games

We develop two efficient procedures for generating cost allocation vectors in the core of a minimum cost spanning tree (m.c.s.t.) game. The first procedure requires O(n ²) elementary operations to obtain each additional point in the core, wheren is the number of users. The efficiency of the second procedure, which is a natural strengthening of the first procedure, stems from the special structure of minimum excess coalitions in the core of an m.c.s.t. game. This special structure is later used (i) to ease the computational difficulty in computing the nucleolus of an m.c.s.t. game, and (ii) to provide a geometric characterization for the nucleolus of an m.c.s.t. game. This geometric characterization implies that in an m.c.s.t. game the nucleolus is the unique point in the intersection of the core and the kernel. We further develop an efficient procedure for generating fair cost allocations which, in some instances, coincide with the nucleolus. Finally, we show that by employing Sterns' transfer scheme we can generate a sequence of cost vectors which converges to the nucleolus. Part of this research was done while the author was visiting the Department of Operations Research at Stanford University. This research was partially supported by Natural Sciences and Engineering Research Council Canada Grant A-4181.     

A Self-Adjusting Algorithm for Driver Scheduling

Public transport driver scheduling is a world wide problem, which is NP-hard. Although some mathematically based methods are being used in the transport industry, there is still much scope for improvements. This paper presents a novel evolutionary approach that simulates the self-adjusting process on a single schedule. Five factors characterized by fuzzy membership functions are first aggregated to evaluate the shift structure. This evaluating function is incorporated into a constructing heuristic to make shift selection. A self-adjusting algorithm is then designed to guide the constructing heuristic to improve a given initial schedule iteratively. In each generation an unfit portion of the working schedule is removed. Broken schedules are repaired by the constructing heuristic until stopping condition is met. Experimental results on real-world driver scheduling problems has demonstrated the success of the proposed approach.     

An Application of Polya's Enumeration Theorem to Partitions of Subsets of Positive Integers

Let S be a non-empty subset of positive integers. A partition of a positive integer n into S is a finite nondecreasing sequence of positive integers a ₁, a ₂,...,a _r in S with repetitions allowed such that . Here we apply Polya's enumeration theorem to find the number P(n; S) of partitions of n into S, and the number DP(n; S) of distinct partitions of n into S. We also present recursive formulas for computing P(n; S) and DP(n; S).     

A property on reinforcing edge-disjoint spanning hypertrees in uniform hypergraphs

Suppose that $H$ is a simple uniform hypergraph satisfying $\left|E\left(H\right)\right|=k(\left|V\left(H\right)\right|?1)$. A $k$-partition $\pi =(X_1,X_2,\dots ,X_k)$ of $E\left(H\right)$ such that $\left|X_i\right|=\left|V\left(H\right)\right|?1$ for $1\le i\le k$ is a uniform $k$-partition. Let $P_k\left(H\right)$ be the collection of all uniform $k$-partitions of $E\left(H\right)$ and define $\epsilon \left(\pi \right)={\sum }_{i=1}^{k}c\left(H\left(X_i\right)\right)?k$, where $c\left(H\right)$ denotes the number of maximal partition-connected sub-hypergraphs of $H$. Let $\epsilon \left(H\right)={min}_{\pi \in P_k\left(H\right)}\epsilon \left(\pi \right)$. Then $\epsilon \left(H\right)\ge 0$ with equality holds if and only if $H$ is a union of $k$ edge-disjoint spanning hypertrees. The parameter $\epsilon \left(H\right)$ is used to measure how close $H$ is being from a union of $k$ edge-disjoint spanning hypertrees.We prove that if $H$ is a simple uniform hypergraph with $\left|E\left(H\right)\right|=k(\left|V\left(H\right)\right|?1)$ and $\epsilon \left(H\right)>0$, then there exist $e\in E\left(H\right)$ and $e^{\prime }\in E\left(H^c\right)$ such that $\epsilon (H?e+e^{\prime })<\epsilon \left(H\right)$. This generalizes a former result, which settles a conjecture of Payan. The result iteratively defines a finite $\epsilon$-decreasing sequence of uniform hypergraphs $H_0,H_1,H_2,\dots ,H_m$ such that $H_0=H$, $H_m$ is the union of $k$ edge-disjoint spanning hypertrees, and such that two consecutive hypergraphs in the sequence differ by exactly one hyperedge.     

On the spanning connectivity of the generalized Petersen graphs P(n,3)

In this paper, we employed lattice model to describe the three internally vertex-disjoint paths that span the vertex set of the generalized Petersen graph $P(n,3)$. We showed that the $P(n,3)$ is 3-spanning connected for odd $n$. Based on the lattice model, five amalgamated and one extension mechanisms are introduced to recursively establish the 3-spanning connectivity of the $P(n,3)$. In each amalgamated mechanism, a particular lattice trail was amalgamated with the lattice trails that was dismembered, transferred, or extended from parts of the lattice trails for $P(n?6,3)$, where a lattice tail is a trail in the lattice model that represents a path in $P(n,3)$.     

广义山路引理的一些应用

具有(CPS)型条件的Ghoussoub-Preiss广义山路引理是经典的AmbrosettiRabinowitz山路引理的一个推广,本文将应用它来研究给定能量的具有对称性或非对称性势能的二阶哈密尔顿系统周期解的存在性.